package com.tgy.algorithm._经典题目01;


import java.util.HashMap;

class Node<K,V> {
    K key;
    V value;
    Node<K,V> pre;
    Node<K,V> next;

    public Node(K key,V value) {
        this.key = key;
        this.value = value;
    }
}

class LRU<K,V> {

    private HashMap<K,Node<K,V>> map;
    private DoubleLinkedList<K,V> list;
    public int cap;

    public LRU(int cap) {
        if (cap <= 0) {
            throw new RuntimeException("cap 不能小于1");
        }
        map = new HashMap<>();
        list = new DoubleLinkedList<>();
        this.cap = cap;
    }

    public void put(K key,V value) {
        Node node = new Node(key, value);
        if (map.keySet().size() < this.cap) {
            map.put(key,node);
        }else {
            Node<K, V> kvNode = list.removeNode();
            map.remove(kvNode.key);
        }
        list.addNode(node);
    }

    public V get(K key) {
        if (!map.containsKey(key)) {
            return null;
        }

        Node<K, V> node = map.get(key);
        list.updateNode(node);
        return node.value;
    }
}

class DoubleLinkedList<K,V> {
    private Node<K,V> head;
    private Node<K,V> tail;

    public void addNode(Node<K,V> node) {
        if (head == null) {
            head = node;
            tail = node;
        }else {
            tail.next = node;
            node.pre = tail;
            node.next = null;
            tail = node;
        }
    }

    public Node<K,V> removeNode() {
        // 没有节点，直接返回
        if (head == null) {
            return null;
        }

        Node<K,V> retNode = head;
        head = head.next;
        retNode.next = null;
        if (head != null) {
            // Node -> Node
            // Node -> Node -> Node
            // 大于1个节点
            head.pre = null;
        }else {
            // Node
            // 有一个节点
            tail = null;
        }
        return retNode;
    }

    public void updateNode(Node<K,V> node) {
        if (node == null) {
            return;
        }
        // 当没有节点和只有一个节点的时候，直接返回，不要做位置改变
        if (head == null || head.next == null) {
            return;
        }

        // node本来就在结尾，不需要做位置改变
        if (tail == node) {
            return;
        }

        // Node -> Node -> Node
        if (head == node) {
            head = node.next;
            head.pre = null;
        }else {
            node.pre.next = node.next;
            node.next.pre = node.pre;
        }

        tail.next = node;
        node.pre = tail;
        tail = node;
    }
}

public class _030_LRU_ {

    public static void main(String[] args) {
        LRU<String, Integer> lru = new LRU<String, Integer>(3);
        lru.put("abc",10);
        lru.put("bbb",20);
        lru.put("bcf",20);
        Integer abc = lru.get("abc");
        System.out.println(abc);
        lru.put("ccc",90);
    }
}
